Let $G$ be an edge-colored graph. A heterochromatic (rainbow, ormulticolored) path of $G$ is such a path in which no two edges have the samecolor. Let $d^c(v)$ denote the color degree and $CN(v)$ denote the colorneighborhood of a vertex $v$ of $G$. In a previous paper, we showed that if$d^c(v)\geq k$ (color degree condition) for every vertex $v$ of $G$, then $G$has a heterochromatic path of length at least $\lceil\frac{k+1}{2}\rceil$, andif $|CN(u)\cup CN(v)|\geq s$ (color neighborhood union condition) for everypair of vertices $u$ and $v$ of $G$, then $G$ has a heterochromatic path oflength at least $\lceil\frac{s}{3}\rceil+1$. Later, in another paper we firstshowed that if $k\leq 7$, $G$ has a heterochromatic path of length at least$k-1$, and then, based on this we use induction on $k$ and showed that if$k\geq 8$, then $G$ has a heterochromatic path of length at least$\lceil\frac{3k}{5}\rceil+1$. In the present paper, by using a simpler approachwe further improve the result by showing that if $k\geq 8$, $G$ has aheterochromatic path of length at least $\lceil\frac{2k}{3}\rceil+1$, whichconfirms a conjecture by Saito. We also improve a previous result by showingthat under the color neighborhood union condition, $G$ has a heterochromaticpath of length at least $\lfloor\frac{2s+4}{5}\rfloor$.
展开▼
机译：令$ G $为边色图。 $ G $的异色（彩虹或多色）路径是这样的路径，其中没有两个边具有相同的颜色。令$ d ^ c（v）$表示色度，$ CN（v）$表示$ G $顶点$ v $的色邻度。在先前的论文中，我们证明了如果$ d ^ c（v）\ geq k $（色度条件）对于$ G $的每个顶点$ v $，则$ G $的异色路径的长度至少为$ \ lceil \ frac {k + 1} {2} \ rceil $，并且如果每对顶点$ u $和$ v $ $ | CN（u）\ cup CN（v）| \ geq s $（颜色邻域联合条件） ，则$ G $的异色路径的长度至少为$ \ lceil \ frac {s} {3} \ rceil + 1 $。后来，在另一篇论文中，我们首先表明，如果$ k \ leq 7 $，$ G $的异色路径的长度至少为$ k-1 $，然后，基于此，我们对$ k $使用归纳法，并证明$ k \ geq 8 $，则$ G $的异色路径的长度至少为$ \ lceil \ frac {3k} {5} \ rceil + 1 $。在本文中，通过使用更简单的方法，我们进一步改善了结果，结果表明，如果$ k \ geq 8 $，$ G $的异色路径的长度至少为$ \ lceil \ frac {2k} {3} \ rceil + 1 $，这证实了斋藤的推测。通过显示在颜色邻域联合条件下，$ G $的异色路径的长度至少为$ \ lfloor \ frac {2s + 4} {5} \ rfloor $，我们还改进了先前的结果。
展开▼
